// 每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

// 二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

// 给定十进制数 N，返回其二进制表示的反码所对应的十进制整数。

//  

// 示例 1：

// 输入：5
// 输出：2
// 解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。
// 示例 2：

// 输入：7
// 输出：0
// 解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。
// 示例 3：

// 输入：10
// 输出：5
// 解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。
//  

// 提示：

// 0 <= N < 10^9

class Solution1 {
public:
    int bitwiseComplement(int N) {
        if (N == 0) return 1;
        int p{32};
        int num{N};
        // 32 - 去除前导0的位数
        while (num) {
            --p;
            num >>= 1;
        }
        return (~(N << p)) >> p;
    }
};

// 先搞个1位2进制数1，这个二进制数小于等于N的时候，将1左移1位，循环到他大于N，这时候再将这个数-1，就得到了与N二进制位数相同的很多1的二进制数，然后相减即可。
class Solution {
public:
    int bitwiseComplement(int N) {
        if (N == 0) return 1;
        int num{1};
        while (num <= N) num <<= 1;
        return num - 1 - N;
    }
};

